import java.util.HashMap;
import java.util.Map;

/**
 * Created With IntelliJ IDEA
 * Description: leetcode:138. 复制带随机指针的链表
 * <a href="https://leetcode.cn/problems/copy-list-with-random-pointer/">...</a>
 * User: DELL
 * Data: 2023-03-05
 * Time: 0:06
 */

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Solution {
    /**
     * 解法一: (哈希表)
     * 利用哈希表将原链表的每一个节点和新 new 出来的节点做关联,之后遍历一遍复原即可.
     * 空间复杂度: O(N)
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        //判空处理
        if (head == null) {
            return null;
        }
        //用hashMap存放每一个结点创建的对应结点
        Map<Node,Node> cacheMap = new HashMap<>();
        //遍历第一遍,创立新结点,并存入map中
        Node cur = head;
        while (cur != null) {
            Node newNode = new Node(cur.val);
            cacheMap.put(cur,newNode);
            cur = cur.next;
        }
        //遍历第二遍,对应复原random域和next域
        cur = head;
        while (cur != null) {
            Node newNode = cacheMap.get(cur);
            newNode.next = cacheMap.get(cur.next);
            newNode.random = cacheMap.get(cur.random);
            cur = cur.next;
        }
        return cacheMap.get(head);
    }

    /**
     * 解法二: (拼接 + 拆分)
     * 第一步: 先进行拼接,即若原链表为 node1 -> node2 -> node3 -> ...
     * 则将其变为 node1 -> 新node1 -> node2 -> 新node2 -> node3 -> 新node3 -> ...
     * 第二步: 遍历将每一个新的节点的 random 域设为 random.next,(这里 null 除外)
     * 第三步: 将拼接好的链表重新分隔开,变成 原链表 和 复制的链表
     * 空间复杂度: O(1)
     * @param head
     * @return
     */
    public Node copyRandomList2(Node head) {
        //判空处理
        if (head == null) {
            return null;
        }
        // 拼接
        Node cur = head;
        while (cur != null) {
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            newNode.random = cur.random;
            cur.next = newNode;
            cur = newNode.next;
        }
        // 调整新节点的 random 域
        cur = head;
        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        // 拆分
        cur = head;
        Node newHead = head.next;
        while (cur != null && cur.next != null) {
            Node temp = cur.next;
            cur.next = cur.next.next;
            cur = temp;
        }
        return newHead;
    }
}